# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def allPossibleFBT(self, n: int):
        if n % 2 == 0:
            return []
        
        ans = []
        root = TreeNode(0)
        if n == 1:
            return root

        def dfs(root, n):
            if n == 0:
                dup = TreeNode(root.val, root.left, root.right)
                ans.append(dup)
                return
            
            root.left = TreeNode(0)
            root.right = TreeNode(0)
            dfs(root.left, n-2)
            dfs(root.right, n-2)
            root.left = None
            root.right = None
        
        dfs(root, n-1)
        return ans


if __name__ == '__main__':
    s = Solution()
    res = s.allPossibleFBT(7)
    print(res)
            
            
